﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;

using Util;

namespace Algorithm.Sort
{
    public class ShellSorter<T> : SorterBase<T>
    {
        [AlgorithmVariation]
        private static void ShellSort(T[] list, IComparer<T> comparer)
        {
            int count = list.Length;
            int increment = count / 2;
            T temp;

            // increment will reduce to 1 at the last loop.
            // and then the last loop is a pure insertion sort.
            while (increment > 0)
            {
                for (int i = increment; i < count; i++)
                {
                    temp = list[i];
                    int j = i - increment;

                    while ((j >= 0) && (comparer.Compare(list[j], temp) > 0))
                    {
                        list[j + increment] = list[j];
                        j -= increment;
                    }

                    list[j + increment] = temp;
                }

                increment /= 2;
            }
        }
    }
}
